Integrated circuits generally contain secret data such as security keys and secret functions. However, different types of attacks can be implemented against integrated circuits from the outside to try to access such data, such as side-channel attacks, electro-migration (such as power consumption, electromagnetic emissions, operations duration, etc.), imaging, fault injection, etc.
To counteract such attacks, solutions based on tamper protection schemes combined with cryptography were proposed, such as Physical unclonable Functions (PUFs), as disclosed in Pappu et. al. in “Physical One-Way Functions”, MIT, March 2001. A PUF is a physical entity which is embodied in a physical structure which is the same in each physical instantiation of the physical entity and which generates a specific output when provided with an input. The value of the specific output is specific to each instantiation of the physical entity embodied within a device. In addition to be tamper-proof in nature, a PUF thus also ensures that the PUF value knowledge of one device does not jeopardize all fabricated devices.
A PUF takes advantage of the variance of conditions in the manufacturing process of many identical devices. A PUF can be incorporated in a CMOS integrated circuit. To some extent, a PUF may be considered as the analog of a fingerprint of the device. A PUF can be used in various contexts (e.g. authentication of chips or goods it is attached to, generation of cryptographic keys or seeds of PRNG, etc).
The physical structure that contains the PUF consists of at least one random component. The output of PUF for a given input is obtained by submitting the input to the physical system in the form of a stimulus, and mapping the behavior that occurs as a result of an interaction between the stimulus and the physical system to an output.
PUFs inherently possess tamper resistant properties. If an attacker tries to disassemble the PUF to observe its operation, this will also disturb the random elements of the PUF and the mapping between the inputs and the outputs. The knowledge of the PUF structure obtained by reverse engineering does not unveil the PUF value.
The value of an output of a PUF for a given challenge is specific to each physical instantiation embodied within a device. A PUF reflects the condition changes in the manufacturing process of otherwise identical structures.
Conventional PUFs include “silicon PUFs” which are fabricated in the same material and through the same process as electronic circuits. This allows embedding PUFs very close to parts of the circuit which process and transmit information. Silicon PUFs are located very close to the cryptographic modules and are thus difficult to tamper with.
Some PUFs, known as “strong” PUFs, have an input and reply differently for each input. Most silicon PUFs are well suited to be strong, since it can have the necessary logic to present the input to the PUF as it awaits it.
An input that a strong PUF accepts is generally referred to as a “challenge” or challenge signal. A challenge is represented by a vector of bits. The output of a PUF is generally referred to as a “response” or “response signal”. A PUF is thus a physical function which maps a digital “Challenge” to a digital “Response”. A response to a given reference challenge is also referred to as an “identifier”. A pair comprising a challenge and the corresponding response of a PUF is referred to as a challenge-response pair.
The interaction between a given challenge and the physical system embodying the PUF cannot be predicted without access to the system. Accordingly, a PUF is hard to characterize. It is unfeasible to obtain the response of a particular PUF for a given challenge without access to the particular physical system underlying the particular PUF. A PUF thus implements a set of challenge-response pairs (CRPs) such that separate logically-identical devices produce different CRPs, unpredictable even to the designer. In other words, a challenge-response pair CRP is coupled to a unique physical device (hence, the “unclonable” property of a PUF). As a result, PUF functions allow identification of objects using their intrinsic physical properties.
A PUF determines an associated response value for a predefined challenge value on the basis of the physical properties of the object. To authenticate an object (i.e. identify the object as the original object), one approach consists in comparing the similarity of the available response values for given challenges, if challenge-response pairs CRPs are known, and the response values provided by the object to be authenticated for these challenges. PUFs can be also used for on-chip determination of a cryptographic key, or for generating a unique identifier such as a cryptographic key for cryptographic purposes.
When handling PUFs, it may be required to assess or test the quality of the PUF devices. The quality of a PUF device may be related to a number of properties or metrics such as:                Steadiness/Reliability: it refers to the property that a response for a given input is replied in a deterministic manner. This property is not only a safety property. Indeed it is also a security issue as an unreliable PUF can accidentally provide the output of another PUF;        Randomness/Unpredictability: it refers to the property that PUFs responses are not predictable, as would be with a serial number, incremented for each device;        Uniqueness: it refers to the property that instances of PUFs differ;        Diffuseness: it refers to the property that the PUF's response to a challenge is unrelated to the challenge, e.g., it is hard to infer an answer from a set of known challenge response pairs. This property concerns specifically “strong PUFs”.        
Such properties have been analyzed in Yohei Hori, Takahiro Yoshida, Toshihiro Katashita and Akashi Satoh, in “Quantitative and Statistical Performance Evaluation of Arbiter Physical Unclonable Functions on FPGAs”, International Conference on Reconfigurable Computing and FPGAs, IEEE, 2010, pp. 298-303.
It is paramount to test these metrics representative of the quality of a PUF both to ensure that the PUF is operational and that it can be used securely. Indeed, if by some means (natural or adversarial), an attacker is able to change the result of a PUF, he/she might succeed in impersonating a device or even in choosing its secret key.
There exist two kinds of tests to assess the quality of a PUF:
1. a test on the abstract model of the PUF, which gives a guarantee that the PUF rationale is sound (Olivier Rioul, Patrick Sol, Sylvain Guilley and Jean-Luc Danger, in “On the Entropy of Physically Unclonable Functions” at 2016 IEEE International Symposium on Information Theory),2. a test on one concrete instance of the PUF.
The second type of test is of major importance because:                the abstract model might not match the reality so that the first test may be worthless, and        an adversary can have changed the PUF via several attacks (for example by destroying it, cutting an essential wire such as a single point of failure, intentionally accelerating its aging, etc.)        
Most of existing tests on PUF have limitations because they are not carried out as online and embedded tests. An “Online” test refers to a test carried out in the field, on the final product using the PUF. An “Embedded” test refers to a test that is computable on the PUF without external connection (which would otherwise be considered a “backdoor”).
There exist on-line and embedded testing of “steadiness/reliability” and “diffuseness”. However, the randomness, unpredictability and uniqueness properties of a PUF are impossible to assess with an embedded test. Indeed, these metrics do not concern a PUF instantiation individually but a “batch of PUFs”. In particular, a major challenge of PUFs relates to test of uniqueness. It is hard to assess the uniqueness of a PUF if the value of the other PUFs of the batch are not known. The uniqueness of a PUF may be defined as the independence among multiple PUFs of responses to the same challenge. The responses from PUFs need to have extremely high uniqueness in order to prevent clones of cryptographic hardware. To warranty uniqueness, manufacturers have to make sure that multiple PUFs with the same challenge-response pairs do not exist, which is costly because each PUF relates to a same PUF batch comprising a huge number of manufactured PUFs and challenge-response pairs.
A PUF is implemented from a unique model and should be manufactured such as every instance of a PUF is different after fabrication. Each instance of a PUF features a behavior which is very little correlated with the other instances of the PUF belonging to a same batch. A small correlation can exist for PUFs which are fabricated close one to each other, but the correlation decreases with the distance. This is due to the working factor of PUFs. Indeed, PUFs rely on small technological variations between instances, which are responsible for the unique behavior of each instance.
Such technological variations are:                independent (e.g., due to the inhomogeneous doping of transistors), and        correlated (e.g., due to surface effects, a part of the wafer where PUFs are implanted can be more doped than another one further apart).        
However, the typical distance of correlation is of the order of a few microns at most and the typical size of a PUF instance is rather of the order of several microns, even in very deep submicron CMOS processes.
Existing approach to assess uniqueness of a PUF are based on querying the identifiers generated by the PUFs of a given batch of PUFs, and to compute the entropy of the identifier (a high entropy meaning a good randomness) and the number of collisions among the identifiers (the fewest collisions, the better the uniqueness). In existing approaches, the estimation of parameters that concern batches of PUFs consists in requesting the responses (e.g., unique identifier) of many or all of PUF instances of a same batch of PUF. Then, based on such database of identifiers, it is possible to test uniqueness and randomness. These properties are called “batch properties”. For example, such approaches are described in:                Yohei Hori, Takahiro Yoshida, Toshihiro Katashita and Akashi Satoh, Quantitative and Statistical Performance Evaluation of Arbiter Physical Unclonable Functions on FPGAs, International Conference on Reconfigurable Computing and FPGAs, 2010, pp. 298-303, and        Abhranil Maiti, Vikash Gunreddy, and Patrick Schaumont, A systematic method to evaluate and compare the performance of physical Unclonable functions, IACR ePrint, vol. 657, pp. 245-267, 2013.        
Such methods are extremely costly and sometimes impossible to carry out.
The measurement of batch properties (randomness and uniqueness) can be needed at various times in the lifecycle of products such as for example:                just after manufacturing;        at boot of the product in the field;        before the PUF is requested (that is, challenged at least once; and/or        sporadically, to check whether no harm or no attack has been perpetrated on the PUF.        
After manufacturing, it is possible to request a PUF response, but this may cause delay in the production line, hence incurring extra costs. Besides, it is possible that a same PUF be used in different products, while the products embedding the PUF are manufactured at different places. Such heterogeneity does not ease the collection of PUF identifiers. In such situations, instead of testing the “batch properties” on all instances of a PUF, the test is conducted on a representative pool of the PUF batch. In most operational environments, the estimation of “batch properties” is practically difficult to realize. For instance, the PUFs can be dispatched in many different devices, which might not all be reachable easily, and at all time. Besides, it is considered a security issue for PUF to disclose its responses. Therefore, it is required that PUFs batch properties can be tested in situ.
There is accordingly a need for online and embedded tests capable of efficiently testing the randomness and uniqueness of a PUF.